package teamproject.graphEditor.graphGenerators;

import java.util.LinkedList;
import java.util.Queue;

import teamproject.graphEditor.Controller;
import teamproject.graphEditor.Node;
import teamproject.graphEditor.NodeFactory;
import teamproject.graphEditor.PDEEdge;
import teamproject.graphEditor.PDEEdgeFactory;
import edu.uci.ics.jung.graph.DirectedGraph;
import edu.uci.ics.jung.graph.DirectedSparseGraph;

/**
 * Class that generates a complete directed tree specified by the depth and the
 * number of children.
 */
public class TreeGenerator implements GraphGenerator {

	private Controller control;
	private int depth;
	private int numberOfChildren;
	private int numberOfNodes; // number of nodes in a complete tree
	private NodeFactory nodefactory;
	private PDEEdgeFactory edgefactory;
	private DirectedGraph<Node, PDEEdge> g;

	/**
	 * Creates an instance of this TreeGenerator with the depth being 3 and the
	 * number of children being 2.
	 * 
	 * @param control
	 *            Controller which contains the node and edge factories
	 */
	public TreeGenerator(Controller control) {
		this(control, 3, 2);
	}

	/**
	 * Creates an instance of this TreeGenerator.
	 * 
	 * @param control
	 *            Controller which contains the node and edge factories
	 * @param depth
	 *            the depth of tree
	 * @param numberOfChildren
	 *            the number of children for each node
	 */
	public TreeGenerator(Controller control, int depth, int numberOfChildren) {
		this.control = control;
		this.depth = depth;
		this.numberOfChildren = numberOfChildren;
		this.nodefactory = control.getNodeFactory();
		this.edgefactory = control.getEdgeFactory();
		this.numberOfNodes = (int) (Math.pow(numberOfChildren, depth + 1) - 1)
				/ (numberOfChildren - 1);
	}

	@Override
	public DirectedGraph<Node, PDEEdge> generateGraph() {
		g = new DirectedSparseGraph<Node, PDEEdge>();
		g = (DirectedGraph<Node, PDEEdge>) control.initNewGraph(g);

		// TODO warum?
		g.addVertex(nodefactory.create());

		if (depth == 0)
			return g;
		else {
			Node root = null;

			for (Node node : g.getVertices()) {
				if (g.inDegree(node) == 0) {
					root = node;
					break;
				}
			}
			generateTree(root);
		}
		return g;
	}

	private void generateTree(Node root) {
		if (root == null)
			throw new NullPointerException(
					"The root for generating a tree has not been set");

		Queue<Node> queue = new LinkedList<Node>();
		queue.offer(root);

		while (g.getVertexCount() != numberOfNodes) {
			Node n = queue.poll();

			for (int i = 0; i < numberOfChildren; i++) {
				g.addEdge(edgefactory.create(), n, nodefactory.create());
			}

			for (Node child : g.getSuccessors(n)) {
				queue.offer(child);
			}
		}
	}
}
